package recursivecode;

import org.apache.commons.lang3.StringUtils;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class AllCode {
	// 1. 爬楼梯
	// 2. 汉诺塔
	// 3. 斐波那契数据
	// 4. 阶乘
	// 5. 逆序一个栈
	// 6. 逆序一个字符串
	// 6. 子序列
	// 8. 子串

	@Test
	public void testStairs() {
		int N = 10;
		int num = getStairsMethodNumber(N);
		System.out.println(String.format("爬 %d 层楼梯,共有 %d 中方案", N, num));
	}

	private int getStairsMethodNumber(int n) {
		if (n <= 0) {
			return 0;
		}

		return parseStairsMethodNumber(n);
	}

	private int parseStairsMethodNumber(int n) {
		if (n == 1) {
			return 1;
		}
		if (n == 2) {
			return 2;
		}

		return parseStairsMethodNumber(n - 1) + parseStairsMethodNumber(n - 2);
	}

	// 2. 汉诺塔
	@Test
	public void testHanniCode() {
		int N = 3;
		getHanniCodeDetail(N);
	}

	private void getHanniCodeDetail(int n) {
		if (n <= 0) {
			return;
		}
		parseHanniCodeDetail(n, "from", "to", "other");
	}

	private void parseHanniCodeDetail(int n, String from, String to, String other) {
		if (n == 1) {
			System.out.println(String.format("move 1 %s 至 %s", from, to));
			return;
		}

		parseHanniCodeDetail(n-1 ,from,other,to	);
		System.out.println(String.format("move %d %s 至 %s", n, from, to));
		parseHanniCodeDetail(n-1,other,to,from);
	}

	//斐波那契数据
	@Test
	public void testFibonacciSequence() {
		int N = 10;
		int num = getFibonacciSequence(N);
		System.out.println(num);

	}

	private int getFibonacciSequence(int n) {
		if (n <=0){
			return 0;
		}
		return parseFibonacciSequence(n);
	}

	private int parseFibonacciSequence(int n) {
		if (n ==1 || n==2){
			return 1;
		}
		return parseStairsMethodNumber(n-1)+parseStairsMethodNumber(n-2);
	}

	@Test
	public void testReverseStack(){
		Stack<String> stack = new Stack<>();
		stack.push("a");
		stack.push("b");
		stack.push("c");
		stack.push("d");
		reverseStack(stack);
	}

	private void reverseStack(Stack<String> stack) {
		if (stack.isEmpty()){
			return;
		}
		String s = parseReverseStack(stack);
		reverseStack(stack);
		stack.push(s);
	}

	private String parseReverseStack(Stack<String> stack) {
		if (stack.size() == 1){
			return stack.pop();
		}
		String pop = stack.pop();
		String res = parseReverseStack(stack);
		stack.push(pop);
		return res;
	}

	@Test
	public void testReverseString(){
		String str = "abcdefg";
		System.out.println(getReverseString(str));
	}

	private String getReverseString(String str) {
		if (str == null || str.length() == 0){
			return StringUtils.EMPTY;
		}
		return parseReverseString(str);
	}

	private String parseReverseString(String str) {
		if (str.length() ==1 ){
			return str;
		}

		String substring = str.substring(1, str.length());
		String result =   parseReverseString(substring);
		result += str.charAt(0);
		return result;
	}

	@Test
	public void testSubsequenceString(){
		String str = "abc";
		List<String> res = getAllSubsequenceString(str);
		System.out.println(res);
	}

	private List<String> getAllSubsequenceString(String str) {
		if (str == null|| str.length() ==0){
			return new ArrayList<>();
		}
		char[] chars = str.toCharArray();
		List<String> result = new ArrayList<>();
		parseAllSubsequenceString(chars,0,"", result);
		return result;
	}

	private void parseAllSubsequenceString(char[] chars, int index,String path, List<String> result) {
		if (index == chars.length){
			result.add(path);
			return;
		}

		String no = path;
		parseAllSubsequenceString(chars,index+1,no,result);
		String yes = path + chars[index];
		parseAllSubsequenceString(chars,index+1,yes,result);
	}

	@Test
	public void testSubstringString(){
		String str = "abc";
		List<String> res = getAllSubstringString(str);
		System.out.println(res);
	}

	private List<String> getAllSubstringString(String str) {
		if (str == null || str.length() ==0){
			return new ArrayList<>();
		}
		List<String> result = new ArrayList<>();
		char[] chars = str.toCharArray();
		parseAllSubstringString(chars,0,"",result);
		return result;
	}

	private void parseAllSubstringString(char[] chars, int index, String path, List<String> result) {

		for (int i = index; i < chars.length; i++) {
			for (int j = i+1; j <= chars.length; j++) {

				parseAllSubstringString(chars,j,path+String.valueOf(chars[i]),result);
			}
		}

		if (index <=chars.length && !result.contains(path)){

			result.add(path);
		}
	}
}
